package com.beaven.java.sort;

/**
 * @author Beaven
 * @date 2018/7/7 20:40
 * <p>
 * 快速排序
 * <p>
 * 思想：找到数组的中间数，把比中间数小的放左边，大的放右边，然后在两边分别再找两个中间数，依次进行放置，
 * 最后的数组即有序。其中最重要的就是找到最优中间数进行合理切分
 */
public class QuickSort {

    public static void sort(int[] nums) {
        // 应该先打乱数组的顺序，消除对输入的依赖
        sort(nums, 0, nums.length - 1);
    }

    private static void sort(int[] nums, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(nums, lo, hi);
        sort(nums, lo, j - 1);
        sort(nums, j + 1, hi);
    }

    private static int partition(int[] nums, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        // 先随意指定lo作为切分元素
        int v = nums[lo];
        while (true) {
            // 从左向右扫描，直到找到一个大于等于v的元素停止
            while (nums[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            // 从右往左扫描，直到找到一个小于等于v的元素停止
            while (v < nums[--j]) {
                if (j == lo) {
                    break;
                }
            }
            // 大于时防止数组越界，等于时出现指针相等，在循环进行数据交换
            if (i >= j) {
                break;
            }
            // 在这里前面找到的i和j两个元素，是不符合v左边的都是小于它，右边都是大鱼它的要求，所以进行一次交换
            exch(nums, i, j);
        }

        exch(nums, lo, j);
        return j;
    }

    private static void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}
